import heapq


class Solution:
    def furthestBuilding(self, heights: list, bricks: int, ladders: int) -> int:
        def canJump(heightDiffs, bricks, ladders, sumDiff):
            if bricks >= sumDiff:
                return True
            heapq.heapify(heightDiffs)
            while len(heightDiffs) > 0:
                if ladders == 0:
                    return bricks >= sumDiff
                height = heapq.heappop(heightDiffs)
                if ladders > 0:
                    ladders -= 1
                    sumDiff += height

            return sumDiff == 0

        heightDiffs = [0 for _ in range(len(heights)+1)]
        sumDiff = 0
        for i in range(1, len(heights)):
            diff = heights[i] - heights[i-1] if heights[i] - \
                heights[i-1] > 0 else 0
            sumDiff += diff
            heightDiffs[i] = -diff

        for i in range(len(heights), 0, -1):
            sumDiff += heightDiffs[i]
            if canJump(heightDiffs[:i], bricks, ladders, sumDiff):
                return i - 1

        return 0
